/*
 * graph.h -- this file is part of mISPL.
 * Copyright (C) 2011 Christian Krause
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */
#include "graph.h"

graph_t graph_init(int nodes) {
	graph_t graph = malloc(sizeof(int) + (sizeof(char) * nodes * nodes));
	graph->nodes = nodes;
	memset(graph->edges, '\0', nodes * nodes);
	return graph;
}

void graph_clear(graph_t graph) {
	free(graph);
}

void graph_add_edge(graph_t graph, int source, int target) {
	graph->edges[(source*graph->nodes) + target] = 1;
}

void graph_remove_edge(graph_t graph, int source, int target) {
	graph->edges[(source*graph->nodes) + target] = 0;
}

path_t path_init(int maxlength) {
	path_t path = malloc(sizeof(int) * (maxlength + 1));
	path->length = 0;
	memset(path->nodes, '\0', maxlength);
	return path;
}

void path_print(path_t path) {
	int i;
	if (path->length<=0) {
		printf("empty\n");
	} else {
		for (i=0; i<path->length; i++) {
			if (i==0) {
				printf("%d", path->nodes[i]);
			} else {
				printf(",%d", path->nodes[i]);
			}
		}
		printf("\n");
	}
}

void path_clear(path_t path) {
	free(path);
}

bool_t graph_complete_path(graph_t graph, path_t path, int end) {
	if (path->length<=0) {
		return FALSE;
	}
	int last = path->nodes[path->length-1];
	if (last==end) {
		return TRUE;
	}
	bool_t visited;
	int offset = (last * graph->nodes);
	int i, j;
	for (i=0; i<graph->nodes; i++) {
		if (graph->edges[offset+i]) {
			visited = FALSE;
			for (j=0; j<path->length; j++) {
				if (path->nodes[j]==i) {
					visited = TRUE;
					break;
				}
			}
			if (!visited) {
				path->nodes[path->length] = i;
				path->length++;
				if (graph_complete_path(graph, path, end)) {
					return TRUE;
				}
			}
		}
	}
	path->length--;
	return FALSE;
}

path_t graph_find_path(graph_t graph, int start, int end) {
	path_t path = path_init(graph->nodes);
	path->nodes[0] = start;
	path->length = 1;
	if (graph_complete_path(graph, path, end)) {
		return path;
	} else {
		path_clear(path);
		return NULL;
	}
}

bool_t graph_exists_path(graph_t graph, int start, int end) {
	path_t path = graph_find_path(graph, start, end);
	bool_t exists = (path!=NULL);
	if (exists) {
		path_clear(path);
	}
	return exists;
}
